The article proposes a formal semantics of happiness and sadness modalities in the imperfect information setting. It shows that these modalities are not definable through each other and gives a sound and complete axiomatization of their properties.

The article studies properties of functional dependencies between strategies of players in Nash equilibria of multiplayer strategic games. The main focus is on the properties of functional dependencies in the context of a fixed dependency graph for payoff functions. A logical system describing properties of functional dependence for any given graph is proposed and is proven to be complete.

The article studies preferences of agents in a setting with imperfect information. For such a setting, the authors propose a new class of preferences. It is said that an agent prefers one statement over another if, among all indistinguishable worlds, the agent prefers the worlds where the first statement is true to those where the second one is true. The main technical result is a sound and complete logical system describing the interplay between a binary modality capturing preferences and the (...) knowledge modality. The proof of completeness is using a newly proposed “tumbled pairs” technique. (shrink)

With agents relying more and more on information from central servers rather than their own sensors, knowledge becomes property not of a specific agent but of the data that the agents can access. The article proposes a dynamic logic of data-informed knowledge that describes an interplay between three modalities and one relation capturing the properties of this form of knowledge. The main technical results are the undefinability of two dynamic operators through each other, a sound and complete axiomatisation, and a (...) model checking algorithm. (shrink)

Betweenness as a relation between three individual points has been widely studied in geometry and axiomatized by several authors in different contexts. The article proposes a more general notion of betweenness as a relation between three sets of points. The main technical result is a sound and complete logical system describing universal properties of this relation between sets of vertices of a graph.

Two different types of functional dependencies are compared: dependencies that are functional due to the laws of nature and dependencies that are functional if all involved agents behave rationally. The first type of dependencies was axiomatized by Armstrong. This article gives a formal definition of the second type of functional dependencies in terms of strategic games and describes a sound and complete axiomatization of their properties. The axiomatization is significantly different from the Armstrong’s axioms.

The article studies knowledge in multiagent systems where data available to the agents may have small errors. To reason about such uncertain knowledge, a formal semantics is introduced in which indistinguishability relations, commonly used in the semantics for epistemic logic S5, are replaced with metrics to capture how much two epistemic worlds are different from an agent’s point of view. The main result is a logical system sound and complete with respect to the proposed semantics.

A relation between two secrets, known in the literature as nondeducibility , was originally introduced by Sutherland. We extend it to a relation between sets of secrets that we call independence . This paper proposes a formal logical system for the independence relation, proves the completeness of the system with respect to a semantics of secrets, and shows that all axioms of the system are logically independent.

The article proposes Logic of Secrets in Collaboration Networks, a formal logical system for reasoning about a set of secrets established over a fixed configuration of communication channels. The system’s key feature, a multi-channel relation called independence, is a generalization of a two-channel relation known in the literature as nondeducibility. The main result is the completeness of the proposed system with respect to a semantics of secrets.

The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality that corresponds to partial recursive function type constructor under the above interpretation. The cases of deterministic and non-deterministic functions are considered and for both of them semantically complete modal logics are described and decidability of these logics is established.

The article proposes Logic of Secrets in Collaboration Networks, a formal logical system for reasoning about a set of secrets established over a fixed configuration of communication channels. The system’s key feature, a multi-channel relation called independence, is a generalization of a two-channel relation known in the literature as nondeducibility. The main result is the completeness of the proposed system with respect to a semantics of secrets.

A new modal logic is introduced. It describes properties of provability by interpreting modality as a deductive closure operator on sets of formulas. Logic is proven to be decidable and complete with respect to this semantics.

Traditionally, the formulae in modal logic express properties of possible worlds. Prior introduced “egocentric” logics that capture properties of agents rather than of possible worlds. In such a setting, the article proposes the modality “know how to tell apart” and gives a complete logical system describing the interplay between this modality and the knowledge modality. An important contribution of this work is a new matrix-based technique for proving completeness theorems in an egocentric setting.

Three different types of interdependence between pieces of information, or "secrets", are discussed and compared. Two of them, functional dependence and non-deducibility, have been studied and axiomatized before. This article introduces a third type of interdependence and provides a complete and decidable axiomatization of this new relation.

Otpor is discussed in the text as a complex and contradictory new type of social movement, whose members attempted to contribute to the tradition of enlightened reform of social and political life in Serbia, simultaneously in a highly pragmatic and in a creative, possibly even irresponsible manner. After the introduction, analyzed are popular and media narratives on the characteristics of the movement, dilemmas concerning the founding of the movement and meaning of its key symbols, and the Faustian question of goals (...) and consequences of foreign, in particular American influences. Following is a discussion of strategic and tactical roles of Otpor in the coordinated project of ousting Milosevic. Otpor?s role is then re-interpreted in the frame of the?electoral revolution?, developed by Valerie Bunce, Sharon Wolchik and Michael McFoul. An assessment of the transformation of Otpor from an active social movement into an exportable blueprint for non-violent political revolutions is offered in lieu of a conclusion. U radu se o Otporu raspravlja kao o slozenom, pa cak i kontradiktornom drustvenom pokretu novog tipa, koji je na krajnje pragmatican, a istovremeno i veoma mastovit, stvaralacki nastrojen, na trenutke cak neozbiljan i neodgovoran nacin pokusao da nastavi tradiciju prosvecenog reformisanja drustvenog i politickog zivota u Srbiji. Autor zapocinje analizu razmatranjem medijskih i narodskih narativa o Otporu. Potom se prelazi na pitanje nastanka pokreta i mogucih znacenja njegovog imena i kljucnih simbola. Sledeci odeljak bavi se "faustovskim" pitanjem vrsta i posledica stranih uticaja na nacin funkcionisanja Otpora. Zatim se prelazi na razmatranje specificnih strateskih i taktickih uloga Otpora u koordinisanom projektu rusenja Milosevicevog rezima. Sledi pokusaj teorijskog odredjenja politickog projekta ciji je konstitutivni deo bio i Otpor, a koji pociva na modelu izborne revolucije koji su razvili Valeri Bans, Seron Volcik i Majkl Mekfaul. U epilogu se razmatra kako je pokret, iako politicki mrtav, zahvaljujuci projektima nekadasnjih aktivista uspeo da preraste u jedan od poznatijih srpskih izvoznih "brendova". (shrink)

The article studies properties of interchangeability of pure, mixed, strict, and strict mixed Nash equilibria. The main result is a sound and complete axiomatic system that describes properties of interchangeability in all four settings. It has been previously shown that the same axiomatic system also describes properties of independence in probability theory, nondeducibility in information flow, and non-interference in concurrency theory.

A new approach to defining complexity of propositional formulas and proofs is suggested. Instead of measuring the size of these syntactical structures in the propositional language, the article suggests to define the complexity by the size of external descriptions of such constructions. The main result is a lower bound on proof complexity with respect to this new definition of complexity.

I would like to support the stand taken by M. I. Budyko in his appeal for expansion of studies of problems of global ecology. The need to organize such investigations is recognized by all. And it is really not all that important whether we call this new science "global ecology" or "biogeocenology." But it must in any case be an alloy of the biological, physical, chemical, and mathematical sciences. In all likelihood, the leading role may at various times and in (...) the study of different problems be played by physicists, mathematicians, biologists, or chemists. (shrink)

The text offers an examination of socio-political bases, modes of functioning, and of the consequences of political instrumentalisation of popular narratives on Serbian disunity. The first section of the paper deals with what is being expressed and what is being done socially when narratives on Serbian disunity are invoked in everyday discourses. The next section investigates what political actor sty, by publicly replicating them, or by basing their speeches on key words of those narratives. The narratives on Serbian disunity are (...) then related to their historical and social contexts, and to various forms of identity politics with which they share common traits. The nineteenth century wars over political and cultural identity, intensified by the struggle between contesting claims to political authority, further channeled by the development of party politics in Serbia and radicalized by conflicts of interest and ideology together provided the initial reasons for the apparition of modern discourses on Serbian disunity and disaccord. Next, addressed are the uninnally solidifying or misinterpreting really existing social problems, or because of intentionally exploiting popular perceptions of such problems, the constructive potential related to existing social conflicts and splits can be completely wasted. What results is a deep feeling of frustration, and the diminishing of popular trust in the political elites and the political process in general. The contemporary hyperproduction of narratives on disunity and disaccord in Serbia seems to be directly related to the incapacity of the party system, and of the political system in general, to responsibly address, and eventually resolve historical and contemporary clashes of interest and identity-splits. If this vicious circle in which the consequences of social realities are turned into their causes is to be prevented, conflicts of interest must be discursively disassociated from ideological conflicts, as well as from identity-based conflicts, and all of them have to be disentangled from popular narratives on splits and disunity. Most important of all, the practice of political instrumentalisation of popular narratives on disunity and disaccord has to be gradually abandoned. U radu se istrazuju istorijske i drustvene osnove narodskih prica o srpskom nejedinstvu i neslozi, kao i posledice njihove politicke instrumentalizacije. Paznja se prvo usmerava na ono sto se narodskim pricama o srpskom nejedinstvu i neslozi najcesce postize u svakodnevnoj komunikaciji. Narodskim pricama se, pre svega, ukazuje na pretpostavljeno nepromenljivo svojstvo srpskog identiteta. Njima se odredjuje i glavni uzrok poraza ili neuspeha, u kom slucaju one neretko prerastaju u jeremijade nad istorijskom sudbinom Srba. Najzad, nesloga se moze predstaviti i kao posledica jednog, ili citavog niza faktora, od mentaliteta ili kulture Srba, pa do tudjinske zavere. U sledecem segmentu rada, istrazuju se vidovi politickog instrumentalizovanja narodskih prica o neslozi i ne jedinstvu Srba, odnosno njihova upotreba kao ogleda, modela i velova. U prvom slucaju, politicki akter narodsko vidjenje stanja stvari koristi kao izgovor za svoje neuspehe, ili kako bi naglasio razlike izmedju sebe, svojih takmaca i pobornika. Narativi o neslozi omogucuju akteru i da usmerava publiku na zeljeni nacin, bilo da zeli da unese nove podele u grupu, zaostrava sukob vec postojecih frakcija i povezuje se sa nekom od njih, ili a uspostavlja izgubljeno jedinstvo grupe. Obe prethodne mogucnosti akter moze iskoristiti da bi obezbedio retoricki veo kojim ce prikriti svoje prave namere. Analiza se potom pomera ka ispitivanju istorijskih i drustvenih osnova prica o srpskom ne jedinstvu. Ratovi oko politickog identiteta iz sredine i druge polovine devetnaestog veka, pojacani trvenjima izmedju rivalskih pretenzija na politicki autoritet, dodatno usanceni razvojem stranackog sistema, i radikalizovani novim oblicima sukoba izmedju interesa, vrednosti i identiteta na pocetku dvadesetog veka, zajedno su uslovili razvoj narativa o srpskom ne jedinstvu i rascepima. Na takvu osnovu su se potom nadovezivali rascepi izazvani dinastickim, konfesionalnim ili nacionalnim razlikama, svi zajedno zacementirani iskustvima ratova i revolucija. Analiza se najzad pomera ka nenameravanim posledicama narodskih prica o srpskom ne jedinstvu i razlicitih oblika njihove politicke instrumentalizacije. Zbog pogresnog predstavljanja ili objasnjavanja stvarnih problem a, karakteristicnog za narodske price, a pogotovu zbog politicke zloupotrebe narodskih prica o tim problemima, konstruktivni potencijal vezan za drustvene konflikte i njihovu narativizaciju biva ozbiljno ugrozen. Sledi duboki osecaj frustracije i opadanje poverenja u politicke elite i politicki proces uopste. U zakljucku se skrece paznja na cinjenicu da je savremeno umnozavanje narodskih prica o srpskom ne jedinstvu, kao i prakse njihove politicke instrumentalizacije, povezano sa nesposobnoscu srpskog partijskog sistema i politickog sistema uopste da se odgovorno suoci sa, a pogotovu da razresi splet istorijskih i savremenih sukoba interesa i identitetskih rascepa koji su izvoriste narodskih prica. (shrink)

The paper considers a commonly used axiomatization of the classical propositional logic and studies how different axiom schemata in this system contribute to proof complexity of the logic. The existence of a polynomial bound on proof complexity of every statement provable in this logic is a well-known open question.The axiomatization consists of three schemata. We show that any statement provable using unrestricted number of axioms from the first of the three schemata and polynomially-bounded in size set of axioms from the (...) other schemata, has a polynomially-bounded proof complexity. In addition, it is also established, that any statement, provable using unrestricted number of axioms from the remaining two schemata and polynomially-bounded in size set of axioms from the first scheme, also has a polynomially-bounded proof complexity. (shrink)

Rad predstavlja pokusaj da se jedna konkretna naucna polemika o temi koja je opterecena znatnim ideoloskim nabojem "zanrovski" preusmeri ka formi naucnog dijaloga, i time ucini plodnijom u naucnom smislu. Glavna pitanja koja se razmatraju ticu se pokusaja teorijskog odredjenja petooktobarske revolucije i uloge koju je pokret "Otpor" imao u njoj. U radu se brani teza da teorijski modeli "talasa demokratizacije" i "izborne revolucije" nude najutemeljenije okvire za razmatranje pitanja koja se u tekstu otvaraju. Kljucni problemi o kojima se u (...) radu raspravlja su sledeci: u kojoj meri oslanjanje na strane izvore i teorijske okvire zakrivljuje uvide u lokalne politicke procese kakva je razlika izmedju "uvezenih" i "izbornih revolucija"; koje su posebnosti izborne revolucije u Srbiji i koje je njeno mesto u "drugom talasu" postkomunisticke demokratizacije; koliki je relativni znacaj stranih i lokalnih inicijativa prilikom organizovanja izbornih revolucija; u cemu je razlika izmedju klasicnih odnosa izmedju davalaca i primalaca politicke pomoci i novih odnosa, koji se zasnivaju na nacelu sinergije; koja su ogranicenja ili-ili logike objasnjenja u razmatranju politicke saradnje stranih i domacih aktera; sta povezuje strategiju nenasilnog otpora, proaktivnu logiku politickog delovanja i Otporov "Plan B"; najzad, postoji li mehanicka veza izmedju prisustva strane pomoci i gubljenja kontrole nad rezultatima izborne revolucije. U zavrsnom odeljku, otvara se pitanje negativnih i pozitivnih aspekata nasledja Otpora kao politickog projekta i nudi pokusaj da se razmatranje o dometima pokreta poveze sa razumevanjem "dinamike nade" kao politickog projekta na kojem je Otpor sistematski radio. (shrink)

The article investigates information flow properties of symmetric multi-party protocols. It gives a sound and complete axiomatic system for properties of the functional dependence predicate that are common to all protocols with the same group of symmetries.

The article studies common knowledge in communication networks with a fixed topological structure. It introduces a non-trivial principle, called the Ryōan-ji axiom, which captures logical properties of common knowledge of all protocols with a given network topology. A logical system, consisting of the Ryōan-ji axiom and two additional axioms, is proven to be sound and complete.

Diffusion in social networks is a result of agents’ natural desires to conform to the behavioral patterns of their peers. In this article we show that the recently proposed “propositional opinion diffusion model” could be used to model an agent’s conformity to different social groups that the same agent might belong to, rather than conformity to the society as whole. The main technical contribution of this article is a sound and complete logical system describing the properties of the influence relation (...) in this model. The logical system is an extension of Armstrong’s axioms from database theory by one new axiom that captures the topological structure of the network. (shrink)